|
計算機科学において、ソフトウェアトランザクショナルメモリ(, STM)は、データベーストランザクションに似た並行性制御機構であり、並列計算を行う際の共有メモリへのアクセス法である。この機構はロックベースの同期を用いた並行性制御の代替手段として機能し、ノンブロッキングな方法で実装される物もある。ここでいうトランザクションとは、共有メモリに対する一連の読み出しと書き込みを実行するコードを意味する。論理的にはこれらの読み出しと書き込みは、時間的なある一点で行われ、他のトランザクションからはその間の状態は見えない。トランザクションを行うためにハードウェアにサポートさせるアイデア(ハードウェアトランザクショナルメモリ)は、1986年に Tom Knight により論文と特許として出された。そのアイデアを普及させたのが Maurice Herlihy と J.Eliot B. Moss である。1995年、Nir Shavit と Dan Touitou がこのアイデアをソフトウェアのみで行うトランザクショナルメモリ (STM) に拡張した。STM は近年非常に研究が進み、実用的な実装も進展している。 == パフォーマンス == 現在のたいていのマルチスレッドアプリケーションでロック技術が使われているのとは異なり、STMは楽観的で、実行中の読み書きを逐一記録し、あるスレッドは他のスレッドが行っていることを考慮せずに、共有メモリに対しての変更を完了する。他の進行中の操作に悪影響を与えない責任を書き込み側に負わせる代わりに、その責任を読み込み側に負わせ、全体のトランザクションが完了した後、読み込み側にアクセス対象のメモリが並行して過去に他のスレッドから変更されていないかを検証させる。この最後の処理、つまりトランザクション中に起きた変更を検証させる処理であるが、この検証により正しいものと確認されたならば、変更は永久なものとして反映される。この処理はコミット (commit) と呼ばれる。また、トランザクションはいつでも中止されることがある(アボートと呼ぶ)。アボートされると、そのトランザクションがそれまでに行った(共有データへの)変更は取り消される(ロールバックされる)。もし、トランザクションが変更が競合したためにコミットできなかったならば、普通トランザクションはアボートされ、成功するまで最初からやり直しする。 この楽観的なアプローチの利点は並列性が向上することである。どのスレッドもリソースにアクセスするために待つ必要がなく、普通は同じロックを使って保護されているひとかたまりのデータ構造に対して、異なるスレッド同士が安全かつ同時にデータ構造内の要素に対してばらばらに変更が可能である。読み出しや変更のたびに複製を作るオーバーヘッドや、トランザクションが失敗した場合にやり直すオーバーヘッドがあるにもかかわらず、たいていの現実にあるプログラムではリソースのコンフリクトはめったに起こらないので、多数のコアを搭載した環境ではロックベースの仕組みで行う以上の良好なパフォーマンスを得られる。 しかし実際には、STM システムも少ないプロセッサ(アプリケーションにもよるが1個から4個)上では細粒度ロックベースのシステムと比較して余分な負荷を受ける。これは主にログ管理に関連するオーバーヘッドとトランザクションを完了する時にかかる時間によるものである。この様な場合でも通常2倍以上遅いわけではないので、STM の概念から得られる利益からするとこのペナルティは正当なものだと、STM 提唱者は考えている。 理論的に(最悪値では)、n個の並列で同時に動作するトランザクションが存在した場合、O(n) のメモリ及びプロセッサ時間を必要とする。実際にはこれらは実装の詳細(オーバーヘッドを避けるのに十分早くトランザクションが失敗するように作られる)によって変化する。しかし、ソフトウェアトランザクショナルメモリよりもロックベースアルゴリズムのほうが理論的に処理時間が短いことがある。 抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)』 ■ウィキペディアで「ソフトウェアトランザクショナルメモリ」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Software transactional memory 」があります。 スポンサード リンク
|